package com.fucius.study.leetcode;

import java.util.*;

/**
 *
 * 7. 二叉树的序列化和反序列化
 * 中文English
 * 设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。
 *
 * 如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。
 *
 * 样例
 * 样例 1：
 *
 * 输入：{3,9,20,#,#,15,7}
 * 输出：{3,9,20,#,#,15,7}
 * 解释：
 * 二叉树 {3,9,20,#,#,15,7}，表示如下的树结构：
 * 	  3
 * 	 / \
 * 	9  20
 * 	  /  \
 * 	 15   7
 * 它将被序列化为 {3,9,20,#,#,15,7}
 * 样例 2：
 *
 * 输入：{1,2,3}
 * 输出：{1,2,3}
 * 解释：
 * 二叉树 {1,2,3}，表示如下的树结构：
 *    1
 *   / \
 *  2   3
 * 它将被序列化为 {1,2,3}
 * 我们的数据是进行 BFS 遍历得到的。当你测试结果 Wrong Answer 时，你可以作为输入调试你的代码。
 *
 * 你可以采用其他的方法进行序列化和反序列化。
 *
 * 注意事项
 * 对二进制树进行反序列化或序列化的方式没有限制，LintCode 将您的 serialize 输出作为 deserialize 的输入，它不会检查序列化的结果。
 */
public class TreeSerialize {
    /**
     * This method will be invoked first, you should design your own algorithm
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    public static String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        List<TreeNode> currentFloor = Arrays.asList(root);
        List<TreeNode> nextFloor;

        StringBuilder builder = new StringBuilder();
        while(currentFloor != null && currentFloor.size() != 0){
            nextFloor = new ArrayList<>();
            for (TreeNode treeNode : currentFloor) {
                if (treeNode == null) {
                    builder.append(",#");
                }else{
                    builder.append(","+treeNode.val);
                    nextFloor.add(treeNode.left);
                    nextFloor.add(treeNode.right);
                }
            }
            currentFloor = nextFloor;
        }
        if (builder.length()>0) {
            return builder.substring(1);
        }
        return "";
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in
     * "serialize" method.
     */
    public static TreeNode deserialize(String data) {
        if (data == null || "".equals(data)) {
            return null;
        }
        String[] params = data.trim().split(",");
        if (params.length==0) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(params[0]));
        int i = 1;
        List<TreeNode> currentFloors = Arrays.asList(root);
        List<TreeNode> nextFloor;
        while (currentFloors != null && currentFloors.size() != 0){
            nextFloor = new ArrayList<>();
            for (TreeNode currentFloor : currentFloors) {
                if(i<params.length &&currentFloor!=null){
                    if (!"#".equals(params[i])) {
                        TreeNode left = new TreeNode(Integer.valueOf(params[i]));
                        currentFloor.left = left;
                        nextFloor.add(left);
                    }
                    i++;
                    if (!"#".equals(params[i])) {
                        TreeNode right = new TreeNode(Integer.valueOf(params[i]));
                        currentFloor.right = right;
                        nextFloor.add(right);
                    }
                    i++;
                }
            }
            currentFloors = nextFloor;
        }

        return root;
    }

    public static void main(String[] args) {

        TreeNode treeNode = deserialize("1,2,#,3,4,#,#,#,#");

        System.out.println(serialize(treeNode));
        System.out.println(serialize(null));
    }
    static class TreeNode{
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }
}
